import numpy as np
import sympy as sp
from sympy import factor_list
import random


def sample_irreducible_polynomial(security_param):
    while True:
        degree = security_param
        coeffs = [0] * (degree + 1)
        coeffs[-1] = 1
        num_ones = max(2, min(degree // 2 + 1, 5))
        positions = random.sample(range(degree), num_ones - 1)
        for pos in positions:
            coeffs[pos] = 1
        poly = np.poly1d(coeffs)
        if is_irreducible_advanced(poly):
            return poly


def is_irreducible_advanced(poly):
    x = sp.symbols('x')
    sympy_expr = sum([coeff * x ** i for i, coeff in enumerate(poly.coeffs[::-1])])
    s_poly = sp.poly(sympy_expr, x, domain='ZZ')
    factors = factor_list(s_poly)
    return len(factors[1]) == 1 and factors[1][0][1] == 1


def fast_interpolation(points, values):
    degree = len(points) - 1
    matrix = []
    for point in points:
        row = [point ** i for i in range(degree, -1, -1)]
        matrix.append(row)
    coefficients = np.linalg.solve(matrix, values)
    # 使用更高精度的数据类型（如np.int64）并检查溢出
    coefficients = np.round(coefficients).astype(np.int64)
    polynomial = np.poly1d(coefficients)
    print(f"Interpolated polynomial: {polynomial}")
    return polynomial